#pragma once 

#include<iostream>

#include<vector>

#include<assert.h>

using namespace std;

namespace my_priority{

  template<class T>
    struct less{
      bool operator()(const T& v1,const T& v2){
        return v1<v2;
      }
    };

  template<class T>
    struct greater{
      bool operator()(const T& v1,const T& v2){
        return v1>v2;
      
      }
    };

  template<class T,class Container = std::vector<T> ,class Compare = less<T>>

    class priority_queue{
      
      public:
        void push(const T& val){
          _con.push_back(val);
          adjust_up(_con.size()-1);
        }

        void pop(){
          
          std::swap( _con[_con.size()-1],_con[0]);
          _con.pop_back();
          adjust_down(0);

        }

        bool empty(){

          return _con.empty();
        }

        size_t size(){

          return _con.size();
        }

        const T& top()const{

          assert(!_con.empty());
          return _con[0];

        }

        void swap(priority_queue& con){
          if(_con!=con._con)
          _con.swap(con._con);
        }

      private:

        void adjust_up(size_t child){
          Compare comfunc;
          size_t parent = child;
          while(parent>0){
            parent = (child-1)/2;
            if(comfunc(_con[parent],_con[child])){
              std::swap(_con[parent],_con[child]);
            }
            child = parent;
          }

        }

        void adjust_down(size_t parent){
          Compare comfunc;
          size_t child = parent*2+1;
          while(child<_con.size()){
            if(child+1<_con.size()&&comfunc(_con[child],_con[child+1])){
              ++child;
            }
            if(comfunc(_con[parent],_con[child])){
              std::swap(_con[parent],_con[child]);
            }
            parent = child;
            child = parent*2+1;
          }

        }

        Container _con;
    };


}
